The present invention refers to a ones counter. More particularly, the present invention relates to an asynchronous ones counter employing a two-dimensional, regular array of like cells. Here, a two-dimensional array is defined as a physical arrangement of cells and their interconnections such that all interconnections between cells can be made without the necessity of interconnections overlapping or crossing over one another. For example, even though the flat printed wires of a printed circuit board are three-dimensional because they have thickness, their flat surfaces that are bonded to the surface of the printed circuit board form a two-dimensional surface of interconnection. If the arrangement of interconnections is such that it is necessary for a wire to cross over another in order to make a connection then the physical arrangement of components and wires is not two-dimensional because the wire must leave the plane of interconnection.
As shown in FIG. 1A, the function of a ones counter is to accept as its input a binary vector consisting of a plurality of N single-bit, binary-level lines whose individual values may be either one or zero and then provide as its output, a ones count word of └(log2N)+1┘ bits that indicates the number of input lines that have a level of one. Considering the example shown in FIG. 1B, the binary vector input (1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0) has sixteen individual bits, eleven of which are ones. Thus, N is 16 and the base-2 logarithm of 16 is 4.0 and 4.0+1 rounded down by the floor function └ ┘ becomes the integer 5, the bit width of the ones count output word whose value is 010112 which is the binary notation for eleven, the number of ones in the input binary vector.
A typical application of a ones counter is exemplified in U.S. Pat. No. 5,761,077 by Shackleford entitled “Graph Partitioning Engine Based on Programmable Gate Arrays” wherein the partition state of a bipartitioned graph is contained within a binary vector where each bit represents the partition state of a vertex in the graph. Each bit can either be a binary one or zero, reflecting the partition assignment of the associated vertex. By counting the number of ones in the partition state vector, the relative balance of vertices between the two partitions can be readily determined. The relative balance of vertices is an important factor in determining a figure of merit for the trial partition expressed in the partition state vector. Since many trial partitions must be tested before obtaining an optimum partition, it is desirable to evaluate the ones count as quickly as possible. An obvious method to one skilled in the art is to place the binary vector in a register that is equal in length to the size of the vector, then shift the register to the right one bit at a time, incrementing a counting register by one each time the least significant bit (LSB) of the binary vector register is a one. This method has the primary disadvantage of being too slow, requiring N clock cycles per evaluation.
Another method in the prior art of counting the ones in a binary vector is to use a carry save adder circuit 40 as illustrated in FIG. 2C. The circuit is asynchronous and can effectively provide a ones count 42 for the binary input vector 41 within a single clock cycle. The carry save adder array is constructed from full adders (FIG. 2A) and half adders (FIG. 2B). The full adder 20 has three inputs A, B, C (21-23) and two outputs consisting of a sum S 24 and a carry Y 25. As shown in the truth table 26, the sum 24 is a one when the number of inputs (21-23) equal to one is odd. The carry 25 is a one when two or more of the inputs (21-23) are one. The half adder 30 has two inputs A 31 and C 32 and two outputs consisting of a sum S 33 and a carry Y 34. As shown in its truth table 35, the half adder's sum 33 is a one when the number of inputs 31, 32 is odd. The half adder's carry 34 is a one only when both inputs 31, 32 are ones.
FIG. 2C illustrates the operation of the carry save adder with the example of FIG. 1B where a 16-bit binary vector 41 (1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0) is accepted as input to the carry save adder to produce a ones count 42 of 010112. The organization of a carry save adder is that of summing trees (e.g., 50, 60, 70) formed of full adders and half adders as required. Within a single summing tree, the sum outputs (24 or 33) of each full adder or half adder are connected to the inputs (21-23 or 31, 32) of subsequent full adders 20 or half adders 30 until there is only a single adder component remaining (e.g., 58) with its sum and carry outputs. The carries (25 or 34) from the adder components above the final adder component are passed to a next summing tree (e.g., from 50 to 60) where they are similarly reduced to a single sum and carry. This is carried out until no further reduction can be achieved (for example, the summation tree 70 is composed only of a single half adder 71 that has no carries out of the summation tree, so it represents the final summation tree). The carries and sums from the summation trees are then added with a conventional two-input carry propagate adder 80 to produce the ones count output word 42 which is equal to the number of ones in the binary input vector 41.
In consideration of integrated circuits wherein regular structures and nonoverlapping interconnections are considered desirable, the use of carry save adder array 40 as a ones counter is disadvantageous due to its irregular structure consisting of separate two-dimensional summing planes 50 (composed of full adders 51-57 and half adder 58), 60 (composed of full adders 61-63), 70 (composed of the half adder 71) connected by a carry propagate adder 80 (composed of half adders 81, 83 and full adder 82). The connections of the carries between the summing planes (50 to 60 and 60 to 70) are effectively three dimensional and thus require that extra metallization layers be provided so that the interconnections can be routed over other interconnections.
It is therefore desirable to provide an asynchronous ones counter that is easily expandable to accept any size input vector wherein the structure is regular and the interconnections between the components are two-dimensional (as previously defined). The present invention achieves these goals.